package com.shm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: shm
 * @dateTime: 2020/12/6 10:09
 * @description: 119. 杨辉三角 II
 * 给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。
 *
 *
 *
 * 在杨辉三角中，每个数是它左上方和右上方的数的和。
 *
 * 示例:
 *
 * 输入: 3
 * 输出: [1,3,3,1]
 * 进阶：
 *
 * 你可以优化你的算法到 O(k) 空间复杂度吗？
 */
public class GetRow {
    public List<Integer> getRow(int rowIndex) {
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i <= rowIndex; i++) {
            List<Integer> temp = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j==0||j==i){
                    temp.add(1);
                }else {
                    temp.add(ans.get(i-1).get(j-1)+ans.get(i-1).get(j));
                }
            }
            ans.add(temp);
        }
        return ans.get(rowIndex);
    }

    /**
     * 解题思路
     * 例如输入索引k = 3, 对应是第 3 + 1 = 4行,得出第4行共有4个值,且每个值为
     * 第一个值为: 1
     * 第二个值为: (n - 1) / 1 = (4 - 1) / 1 = 3
     * 第三个值为: (n - 1) / 1 * (n -2) / 2 = (n - 1)(n - 2)/ (1 * 2) = (4-1)(4-2)/(12) = 3
     * 第四个值为: (n - 1) / 1 * (n - 2) / 2 * (n-3)/3 = (n-1)(n-2)(n-3)/(123) =
     * * (4-1)(4-2)(4-3)/(12*3) = 1
     * 由此得出规律:
     * 索引为n-1的行为n,且该行共有n个值(n > 1),得出第n行每个值为:
     * 后一个值等于前一个值然后乘以(n - i) / i
     * 即numVal = (n - i) / i * res.get(i - 1)
     *
     * 作者：jun-mo-xiao-21
     * 链接：https://leetcode-cn.com/problems/pascals-triangle-ii/solution/zhao-gui-lu-qiu-jie-yang-hui-san-jiao-mei-yi-xing-/
     * @param rowIndex
     * @return
     */
    public List<Integer> getRow_2(int rowIndex) {
        List<Integer> res = new ArrayList<>(rowIndex + 1);
        int numRows = rowIndex + 1;
        for (int index = 0; index < numRows; index++) {
//            if (index == 0) {
//                res.add(1);
//            } else {
//                long eachValOfRow = (long) res.get(index - 1) * (long) (numRows - index) / index;
//                res.add((int) eachValOfRow);
//            }

//            还能继续优化，因为每一行两边都是对称的，可以节省一半算力
            if (index == 0) {
                res.add(1);
            }else if(index>numRows/2) {
                res.add(res.get(numRows-1-index));
            } else {
                long eachValOfRow = (long) res.get(index - 1) * (long) (numRows - index) / index;
                res.add((int) eachValOfRow);
            }
        }
        return res;
    }

}
